The present invention relates to a data transfer network for transferring data in the form of packets.
With recent progress of the LSI technology, a parallel computer system with high performance has become possible by interconnecting a number of high-speed, large-capacity processors and carrying out the parallel processing. In such a system, a large amount of data requires to be transferred among processors, between processors and memories, and so on. Therefore, a data transfer network as shown in FIG. 1A, for example, is required for interconnecting processors. Conventional methods of arranging data transfer networks are explained in detail, for example, in an article by Tse-yun Feng, "A survey of interconnection network", IEEE Trans. Computers Vol C-14, No. 12, pp. 12-27 (1981).
There are known data transfer networks using crossbar switches or multi-staged switches. In these systems, the data to be transferred is added with the target address, and then delivered into the data transfer network in the form of packets. In response to the packets, transmission paths are sequentially created in the network.
In case of the data transfer network composed of crossbar switches, the required amount of hardware becomes enormous and such a network is difficult to implement in practice. Therefore, the system using multi-staged switches is more realistic. In this case, the length of data is normally more than several bits, and the target address also requires more than several bits when several thousands or more processors are employed. It is of course desired that the whole bits of each packet are transferred in parallel for high-speed transfer of the packets. However, if the system is designed to transfer the whole bits of each packet in parallel, the numbers of signal lines and switches would become very large. Meanwhile, the data transfer path inherently has a relatively small bit width d (as much as 10 or less bits). From the viewpoint of practice, therefore, it is more advantageous to divide each of packets into a plurality of subpackets each composed of plural bits d, as shown in FIG. 1B, so that the whole bits in each subpacket are transferred in parallel, while different packets are sequentially transferred. In addition to data, the target address also requires to be divided into at least two or more partial addresses.
Each of multi-staged switches jointly constituting a data transfer network judges the destination of the packet input thereto based on the target address included in the packet, and then makes proper switching operation for delivering the packet to the appropriate output port. Even when the data and target address are divided as mentioned above, such switching operation can be made by each switch after waiting for arrival of all the partial addresses. Once switching is established, data subpackets which are sequentially transmitted following the target address, can now be pipelined to the succeeding switch. However, if each switch makes its switching operation after waiting for all the partial addresses, there would give rise a problem that the start time of switching is delayed to a larger extent than with the case where the whole bits of the target address are transferred in parallel.